A computer network is a geographically distributed collection of interconnected subnetworks for transporting data between network nodes, such as computers. A local area network (LAN) is an example of such a subnetwork. The network's topology is defined by an arrangement of client nodes that communicate with one another, typically through one or more intermediate network nodes, such as routers or switches. As used herein, a client node is a network node that is configured to originate or terminate communications over the network. In contrast, an intermediate network node is a node that facilitates routing data between client nodes. Communications between network nodes are typically effected by exchanging discrete packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
The data packets transferred among the network nodes may include fixed-sized data cells and/or variable-sized data frames. Each data packet typically comprises “payload” data prepended (“encapsulated”) by at least one network header formatted in accordance with a network communication protocol. The network headers include information that enables the client nodes and intermediate nodes to route the packet efficiently through the computer network. Often, a packet's network headers include at least a data-link (layer 2) header and an internetwork (layer 3) header, as defined by the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
In operation, a client node may send a data packet to a network interface of an intermediate network node. Thereafter, the intermediate network node receives the packet and forwards the packet to its next destination. For example, the intermediate network node may perform a layer-2 switching function that simply re-directs the packet from one network interface to another based on the contents of the packet's data-link header. Alternatively, the intermediate network node may perform a layer-3 routing function, or forwarding decision, that selects the most appropriate network interface to forward the packet based on the contents of the packet's internetwork header.
Data packets are used to transport many forms of information, including voice and video information, over networks and subnetworks. For instance, voice information may be transmitted in accordance with the Voice over Internet Protocol (VoIP). VoIP refers to a group of technologies used to transmit voice information over data networks from a source node to a destination node. The source and destination nodes employ voice agents that convert voice information from its traditional telephony form to a form that is suitable for packet transmission. In other words, the source node's voice agent encodes, compresses and encapsulates the voice information into a plurality of data packets, and the destination node's voice agent performs complementary functions to decapsulate, uncompress and decode the VoIP packets. Examples of voice agents include IP telephones, VoIP gateways, certain private branch exchanges (PBXs), personal computers (PCs) running communication applications, network devices providing voice gateway services, etc.
Similarly, video information may be carried by various technologies that include video conferencing. Here, data may be processed in much the same fashion as VoIP systems such that a video agent at a source node encodes, compresses and encapsulates voice and video information into packets and transfers the packets over a data network to a video agent at a destination node. The destination node's video agent may decapsulate, uncompress and decode the voice and video information and present it accordingly.
A source node (sender) may be configured to transfer a unidirectional stream of data packets, or a “data flow,” to a destination node (receiver) in a data network. The data flow may comprise, for example, voice or video information. The data flow is unidirectional in that data travels one-way from the sender to the receiver. The logical procession of network nodes that transmit and receive data packets from the sender to the receiver defines the data flow's data path. A first node that is nearer the receiver in the data flow's data path than a second node in the path is said to be “downstream” from the second node. Likewise, a first node that is nearer the sender in the data flow's path than a second node in the path is said to be “upstream” from the second node.
As used herein, an “application instance” is broadly defined as a set of one or more related data flows. More specifically, the data flows in the application instance are related such that loss or corruption of any one of the flows affects the utility of the other flows. For example, an application instance may comprise two opposing data flows that transport voice information in a telephone call. In other words, a first data flow may transport one caller's voice from node A to node B, and a second (opposing) data flow may carry the voice data of the other participant from node B to node A. In this case, loss of either of the data flows may render the telephone call useless.
It should be noted that application data flows need not be symmetrical, as described above in terms of a conventional telephone call. For example, an application instance may have one or two data sources and many receivers, the route from node A to node B may materially differ from the route from node B to node A, or network nodes participating in the same application instance may use different software applications, such as having only a few nodes send video data flows but all send audio, shared whiteboard data or text.
Some data flows are associated with a certain level of quality of service (QoS). For example, a data flow's QoS may specify minimum end-to-end latency or bandwidth requirements needed to support the flow. The Resource reSerVation Protocol (RSVP) is a network-control protocol that enables source and destination nodes to “reserve” the necessary resources to establish the data flow in accordance with the flow's required QoS. RSVP works in conjunction with routing protocols to, e.g., reserve resources along a data path between the source and destination nodes to establish a level of QoS required by the data flow. RSVP is defined in R. Braden, et al., “Resource ReSerVation Protocol (RSVP),” Request For Comments (RFC) 2205, which is hereby incorporated by reference as though fully set forth herein.
In a typical arrangement, the source node sends a RSVP Path message identifying itself and indicating the minimum bandwidth needed to receive the data flow. The Path message proceeds hop-by-hop through the data path, making each intermediate network node aware that a reservation of resources later may be requested. The destination node receives the RSVP Path message and responds with a “request for resources” in the form of a RSVP reservation request (Resv message) which travels hop-by-hop back to the source node. At each hop, the corresponding intermediate network node sets aside sufficient resources to provide the requested bandwidth for the desired data flow. These resources are consequently made available to the data flow so that the data packets of the flow get appropriate QoS treatment.
If sufficient resources are not available, an intermediate network node may “reject” the Resv message (i.e., does not continue forwarding it), generate a reserve error (ResvErr) message and forward the ResvErr message downstream over the path to the destination node. The destination node eventually receives the ResvErr message and concludes that the reservation has failed. A destination node whose Resv message has been rejected may later re-attempt to acquire the resources by re-transmitting another Resv message. Source nodes are unaffected by this process, and they continue to send Path messages to refresh their state.
As defined in RFC 2205, a RSVP data flow is “admitted” and resources allocated to the data flow using a capacity-based admission control technique. According to this technique, resources are allocated to data flows on a “first-come-first-admitted” basis until the capacity of the resources is exhausted. S. Herzog, “RSVP Extensions for Policy Control,” RFC 2750, which is hereby incorporated by reference as though fully set forth herein, defines an extension to RFC 2205 that incorporates policy-based admission control. Through this extension to RSVP, admission control involves reserving resources on a policy basis in addition to using capacity as a basis. A simple example of such is an authentication/authorization policy. If a person attempts to reserve bandwidth but is unknown to the administration or makes an unauthorized request, the request will be denied based on the authentication/authorization policy even though bandwidth is available. But among authorized requesters, bandwidth is granted on a first-come-first-admitted basis.
A policy often employed in conjunction with RFC 2750 is a preemption-priority-based policy described in S. Herzog, “Signaled Preemption Priority Policy Element,” RFC 3181, which is hereby incorporated by reference as though fully set forth herein. The preemption-priority-based policy incorporates a technique that allows a new reservation to preempt one or more existing lower priority reservations in order to acquire resources reserved for the lower priority reservations. According to the technique, a preemption-priority value is associated with a new reservation and defending-priority values are associated with respective existing reservations. The reservations' preemption and defending priority values may be assigned in various ways known in the art. The preemption-priority value for the new reservation is compared with the defending-priority values of existing reservations to determine if the new reservation “preempts” any existing lower priority reservations. If so, resources allocated to selected lower priority reservations are reallocated for the new reservation.
In practice, a Resv message either contains the preemption-priority value associated with the new reservation or a default preemption-priority value is assigned to the reservation request if it does not already contain one. A network node that receives the Resv message may first determine if sufficient unallocated resources are immediately available to satisfy the resources requested in the Resv message. If not, the node then may identify lower priority existing reservations that may be preempted to meet the needs of the new reservation. This may be done by comparing the new reservation's preemption priority value with the defending priority value of an existing reservation to determine if the new reservation is higher in priority than the existing reservation. If so, the network node may preempt the existing reservation by “tearing it down” and reallocating the resources associated with the torn down reservation to the new reservation. Thereafter, a ResvErr message is sent downstream along the data path to notify the downstream nodes, including the destination node, of the preemption.
In conventional implementations, when there are multiple low-priority reservations that are eligible to be preempted, i.e., having defending-priority values less than the new reservation's preemption-priority value, any one of the low-priority reservations may be selected and preempted. Then, the state corresponding to the selected reservation is torn down and its resources reallocated for the new reservation's data flow. Accordingly, an application instance (if one exists) containing the torn-down data flow may be negatively affected, or “disrupted,” as a result of the preemption. That is, the utility of the remaining data flows in the application instance may be significantly diminished unless the torn-down data flow is re-established. Note that in prior-art implementations these “low utility” flows are not themselves preempted and are no more likely to be preempted in the future than any other flow of the same defending-priority value.
When it is required that two or more reservations are preempted, it is desirable to minimize the number of application instances that are disrupted. Thus, for example, if it is necessary to preempt one reservation in each direction over a single communications link, it would be best to preempt two reservations that correspond to the same application instance (e.g., the same telephone call). However, because conventional preemption techniques do not intelligently select which reservations to preempt, it is not likely that two randomly-selected reservations will correspond to the same application instance.
As a simple example, consider two network nodes A and B at opposite ends of a communications link. Assume the link is carrying its full capacity of reservations, and that each reservation corresponds to one direction of a bi-directional voice call. Further, assume all calls have identical bandwidth needs, and that there are two preemption priorities: high and low. When a new high-priority call begins, a Resv message arrives at node A to reserve resources for the new call. In response, the node A selects an existing low-priority call to preempt and reallocates the preempted call's resources, such as bandwidth and memory usage, for the new, high-priority call.
Soon afterwards, a Resv message for the other direction of the high-priority call arrives at node B. Accordingly, the node B also needs to preempt a reservation. Even though node B may now know which reservation was preempted by node A, it needs to preempt a reservation in the other direction, and there is no easy way for node B to determine which, among all the reservations previously installed, is the “partner” reservation to the one just preempted by node A. Thus, the node B selects a reservation to preempt, with significant likelihood of disrupting another call unrelated to the one disrupted by the node A.
In circuit or virtual circuit networks, this problem would typically be dealt with by treating each call (i.e., application instance) as a separate bi-directional virtual circuit having forward and return data paths. As such, when a call is preempted, the call's virtual circuit is torn down, thereby freeing resources in two directions. While this solution effectively reallocates resources for application instances consisting of two opposing data flows, such a solution does not address more complex application instances, e.g., having more than two constituent data flows or having data flows in the same direction. Furthermore, no mechanism currently exists for connectionless (datagram) networks to determine reliably whether two or more selected low-priority reservations correspond to data flows in the same application instance.